package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * LCP 52. 二叉搜索树染色
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/12 17:24
 */
public class GetNumber {


    public static void main(String[] args) {
        GetNumber test = new GetNumber();

        TreeNode root = TreeNode.getInstance15();
        int[][] arr = {{1, 2, 4}, {1, 1, 3}, {0, 3, 5}};

        int number = test.getNumber(root, arr);
        System.out.println(number);
    }

    private List<Integer> list = new ArrayList<>();

    public int getNumber(TreeNode root, int[][] ops) {
        find(root);
        Collections.sort(list);
        TreeMap<Integer, Integer> map = new TreeMap<>();
        Map<Integer, Integer> con = new HashMap<>();
        int size = list.size();
        for (int i = 0; i < size; i++) {
            con.put(list.get(i), i);
        }
        int[] arr = new int[size];
        int length = ops.length;
        for (int i = length - 1; i >= 0; i--) {
            int[] op = ops[i];
            int st = con.get(op[1]);
            int end = con.get(op[2]);
            int a = -1;
            int b = -2;
            for (int j = st; j <= end; j++) {
                if (arr[j] != 0) {
                    if (b == j - 1) {
                        map.put(a, b);
                    }
                    j = map.get(map.floorKey(j));
                    a = -1;
                } else {
                    if (map.get(j) != null) {
                        if (b == j - 1) {
                            map.put(a, b);
                        }
                        j = map.get(j);
                        a = -1;
                    } else {
                        if (a == -1) {
                            a = j;
                        }
                        arr[j] = op[0] + 1;
                        b = j;
                        if (j == end) {
                            map.put(a, b);
                        }
                    }
                }
            }
        }
        int count = 0;
        for (int i : arr) {
            if (i == 2) {
                count++;
            }
        }
        return count;
    }

    private void find(TreeNode node) {
        if (node == null) {
            return;
        }
        list.add(node.val);
        find(node.left);
        find(node.right);
    }

}
